package moon.utils;

import java.io.File;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;


import moon.core.classdef.ClassDef;
import moon.core.classdef.LocalDec;
import moon.core.instruction.CompoundInstr;
import moon.core.instruction.Instr;

import org.apache.log4j.PropertyConfigurator;
import org.jgraph.graph.DefaultEdge;
import org.jgrapht.Graph;
import org.jgrapht.alg.CycleDetector;
import org.jgrapht.alg.KruskalMinimumSpanningTree;
import org.jgrapht.alg.StrongConnectivityInspector;
import org.jgrapht.graph.DirectedSubgraph;
import org.jgrapht.graph.SimpleDirectedGraph;
import org.jgrapht.traverse.TopologicalOrderIterator;


/**
 * Utility class for using with Graphs and JGraphT library with MOON.
 * 
 * @author rmartico
 * 
 */
public class GraphUtil {
	
	public static <T> List<T> getOutgoingVertex(T vertex, SimpleDirectedGraph<T,DefaultEdge> graph){
		List<T> result = new ArrayList<T>();
		Set<DefaultEdge> set = graph.outgoingEdgesOf(vertex);
		for (DefaultEdge de : set) {
			result.add((T)graph.getEdgeTarget(de));
		}
		return result;
	}

	public static <T> List<DirectedSubgraph<T, DefaultEdge>> getCycles(
			SimpleDirectedGraph<T, DefaultEdge> graph) {
		List<DirectedSubgraph<T, DefaultEdge>> cycles = new ArrayList<DirectedSubgraph<T, DefaultEdge>>();
		List<DirectedSubgraph<T, DefaultEdge>> stronglyConnectedSubgraphs = getStronglyConnectedSubgraphs(graph);
		for (DirectedSubgraph<T, DefaultEdge> candidateCycle : stronglyConnectedSubgraphs) {
			if (candidateCycle.vertexSet().size() > 1) {
				cycles.add(candidateCycle);
			}
		}
		return cycles;
	}
	
	public static <T> List<T> getTopologicalOrder(SimpleDirectedGraph graph) {
		List<T> vertex = new ArrayList<T>();
		TopologicalOrderIterator toi = new TopologicalOrderIterator(graph);
		while(toi.hasNext()){
			vertex.add((T)(toi.next()));
		}		
		return vertex;
	}


	public static <T> List<DirectedSubgraph<T, DefaultEdge>> getStronglyConnectedSubgraphs(
			SimpleDirectedGraph<T, DefaultEdge> graph) {
		StrongConnectivityInspector<T, DefaultEdge> sci = new StrongConnectivityInspector<T, DefaultEdge>(
				graph);
		return sci.stronglyConnectedSubgraphs();
	}

	public static <T> SimpleDirectedGraph<T, DefaultEdge> removeCyclesWithDFS(
			SimpleDirectedGraph<T, DefaultEdge> graph,
			T begin) {
		List<T> visited = new ArrayList<T>();
		List<DefaultEdge> edges = new ArrayList<DefaultEdge>();
		// At the beginning all nodes are white...
		Map<T, Color> state = new HashMap<T, Color>();
		for (T cd : graph.vertexSet()) {
			state.put(cd, Color.WHITE);
		}
		//T begin = (T) (graph.vertexSet().toArray()[0]);
		System.out.println("DFS: Begin vertex " + begin.toString());
		visited.add(begin);
		visitDFS(begin, graph, visited, state, edges);
		for (DefaultEdge de : edges) {
			System.out.println(graph.getEdgeSource(de) + " -> " + graph.getEdgeTarget(de));
		}
		SimpleDirectedGraph<T, DefaultEdge> result = new SimpleDirectedGraph<T, DefaultEdge>(DefaultEdge.class);
		for (T cd : graph.vertexSet()) {
			result.addVertex(cd);
		}
		for (DefaultEdge de : edges) {
			result.addEdge(graph.getEdgeSource(de), graph.getEdgeTarget(de));
		}
		return result;
	}

	private static <T> void visitDFS(T begin,
			SimpleDirectedGraph<T, DefaultEdge> graph,
			List<T> visited,
			Map<T,Color> state,
			List<DefaultEdge> edges) {
		System.out.println(begin.toString());
		state.put(begin, Color.GRAY);
		Set<DefaultEdge> outgoing = graph.outgoingEdgesOf(begin);
		for (DefaultEdge out : outgoing) {
			T end = graph.getEdgeTarget(out);
			if (state.get(end)!=Color.GRAY){ 
				// an edge from gray to gray is a back edge
				// a back edge includes a cycle in the graph !!!
				edges.add(out);
			}
			if (!visited.contains(end)) {
				visited.add(end);
				visitDFS(end, graph, visited, state, edges);
			}
		}
		// when all adyacents have been visited the node is black
		state.put(begin, Color.BLACK);
	}

	enum Color {
		WHITE, GRAY, BLACK
	}

}
